# 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
#
# 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
#
# 输入：target = 9
# 输出: [[2,3,4],[4,5]]

# 输入：target = 15
# 输出：[[1,2,3,4,5],[4,5,6],[7,8]]


# https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof


# 道理我都懂 应该是从目标开始减法运算比较效率
# 然而不知道为什么突然转不过来了 so 我还是写个加法版吧...
# 执行用时 : 1012 ms 击败了 5.57% 的用户
# 内存消耗 : 13.4 MB 击败了 100.00% 的用户

def findContinuousSequence(target: int):
    check_head = 1
    check_tail = check_head + 1
    result = []
    while check_tail < target:
        put_out = list(range(check_head, check_tail))
        if sum(put_out) < target:
            check_tail += 1
        elif sum(put_out) > target:
            check_head += 1
        else:
            result.append(put_out)
            check_tail += 1
            check_head += 1
            continue

    return result


# 复盘:
# 去抄答案 看到一个差不多的解法 取了个中位数,看起来能减少一半的循环
# 借鉴了一下改进版


def findContinuousSequence_2(target: int):
    check_head = 1
    check_tail = check_head + 1
    middle = (target // 2) + 1
    result = []
    while check_head <= middle:
        put_out = list(range(check_head, check_tail))
        if sum(put_out) < target:
            check_tail += 1
        elif sum(put_out) > target:
            check_head += 1
        else:
            result.append(put_out)
            check_tail += 1
            check_head += 1
            continue

    return result


# 执行用时 :528 ms 击败了 22.26%的用户
# 内存消耗 : 13.3 MB 击败了 100.00% 的用户

# 用时方面改进了一点点w
